SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Maze-solving algorithm</title>

</head>

Maze-solving algorithm

</h1>

</header>

A maze-solving algorithm is an <a href="Algorithm" title="Algorithm">automated method</a> for solving a <a href="Maze" title="Maze">maze</a>. The random mouse, wall follower, Pledge, and Trémaux's <a href="Algorithm" title="Algorithm">algorithms</a> are designed to be used inside the maze by a traveler with no prior knowledge of the maze, whereas the <a href="Cul-de-sac" class="mw-redirect" title="Cul-de-sac">dead-end</a> filling and <a href="Shortest_path_algorithm" class="mw-redirect" title="Shortest path algorithm">shortest path algorithms</a> are designed to be used by a person or computer program that can see the whole maze at once.

Mazes containing no loops are known as "simply connected", or "perfect" mazes, and are equivalent to a <a href="Tree_(graph_theory)" title="Tree (graph theory)">tree</a> in graph theory. Maze-solving algorithms are closely related to <a href="Graph_theory" title="Graph theory">graph theory</a>. Intuitively, if one pulled and stretched out the paths in the maze in the proper way, the result could be made to resemble a tree.<a href="#cite_note-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Random_mouse_algorithm">Random mouse algorithm</h2></div>

This simple method can be implemented by a very unintelligent <a href="Robot" title="Robot">robot</a> or perhaps a mouse, because it does not require any memory. The robot proceeds following the current passage until a junction is reached, and then makes a random decision about the next direction to follow. Although such a method would always <a href="Las_Vegas_algorithm" title="Las Vegas algorithm">eventually find the right solution</a>, the algorithm can be very slow.<a href="#cite_note-Aleliunas1979-2">[2]</a>

One effective rule for traversing mazes is the Hand On Wall Rule, also known as either the left-hand rule or the right-hand rule. If the maze is <a href="Simply_connected_space" title="Simply connected space">simply connected</a>, that is, all its walls are connected together or to the maze's outer boundary, then by keeping one hand in contact with one wall of the maze the solver is guaranteed not to get lost and will reach a different exit if there is one; otherwise, the algorithm will return to the entrance having traversed every corridor next to that connected section of walls at least once. The algorithm is a depth-first in-order <a href="Tree_traversal" title="Tree traversal">tree traversal</a>.

Another perspective into why wall following works is topological. If the walls are connected, then they may be deformed into a loop or circle.<a href="#cite_note-3">[3]</a> Then wall following reduces to walking around a circle from start to finish. To further this idea, notice that by grouping together connected components of the maze walls, the boundaries between these are precisely the solutions, even if there is more than one solution.

If the maze is not simply-connected (i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not necessarily reach the goal.

Another concern is that care should be taken to begin wall-following at the entrance to the maze. If the maze is not simply-connected and one begins wall-following at an arbitrary point inside the maze, one could find themselves trapped along a separate wall that loops around on itself and containing no entrances or exits. Should it be the case that wall-following begins late, attempt to mark the position in which wall-following began. Because wall-following will always lead you back to where you started, if you come across your starting point a second time, you can conclude the maze is not simply-connected, and you should switch to an alternative wall not yet followed. See the Pledge Algorithm, below, for an alternative methodology.

Wall-following can be done in 3D or higher-dimensional mazes if its higher-dimensional passages can be projected onto the 2D plane in a deterministic manner. For example, if in a 3D maze "up" passages can be assumed to lead Northwest, and "down" passages can be assumed to lead southeast, then standard wall following rules can apply. However, unlike in 2D, this requires that the current orientation is known, to determine which direction is the first on the left or right.

A simulation of this algorithm working can be found <a rel="nofollow" class="external text" href="https://scratch.mit.edu/projects/1049044916/">here</a>.

<div class="mw-heading mw-heading2"><h2 id="Pledge_algorithm">Pledge algorithm</h2></div>

Disjoint (where walls are not connected to the outer boundary/boundary is not closed) mazes can be solved with the wall follower method, so long as the entrance and exit to the maze are on the outer walls of the maze. If however, the solver starts inside the maze, it might be on a section disjoint from the exit, and wall followers will continually go around their ring. The Pledge algorithm (named after Jon Pledge of Exeter) can solve this problem.<a href="#cite_note-4">[4]</a><a href="#cite_note-5">[5]</a>

The Pledge algorithm, designed to circumvent obstacles, requires an arbitrarily chosen direction to go toward, which will be preferential. When an obstacle is met, one hand (say the right hand) is kept along the obstacle while the angles turned are counted (clockwise turn is positive, counter-clockwise turn is negative). When the solver is facing the original preferential direction again, and the angular sum of the turns made is 0, the solver leaves the obstacle and continues moving in its original direction.

The hand is removed from the wall only when both "sum of turns made" and "current heading" are at zero. This allows the algorithm to avoid traps shaped like an upper case letter "G". Assuming the algorithm turns left at the first wall, one gets turned around a full 360 <a href="Degree_(angle)" title="Degree (angle)">degrees</a> by the walls. An algorithm that only keeps track of "current heading" leads into an infinite loop as it leaves the lower rightmost wall heading left and runs into the curved section on the left hand side again. The Pledge algorithm does not leave the rightmost wall due to the "sum of turns made" not being zero at that point (note 360 <a href="Degree_(angle)" title="Degree (angle)">degrees</a> is not equal to 0 <a href="Degree_(angle)" title="Degree (angle)">degrees</a>). It follows the wall all the way around, finally leaving it heading left outside and just underneath the letter shape.

This algorithm allows a person with a compass to find their way from any point inside to an outer exit of any finite two-dimensional maze, regardless of the initial position of the solver. However, this algorithm will not work in doing the reverse, namely finding the way from an entrance on the outside of a maze to some end goal within it.

<div class="mw-heading mw-heading2"><h2 id="Trémaux's_algorithm">Trémaux's algorithm</h2></div>

Trémaux's algorithm, invented by <a href="Charles_Pierre_Tr%C3%A9maux" class="mw-redirect" title="Charles Pierre Trémaux">Charles Pierre Trémaux</a>,<a href="#cite_note-6">[6]</a> is an efficient method to find the way out of a maze that requires drawing lines on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages,<a href="#cite_note-Récréations_Mathématiques-7">[7]</a> but it is not guaranteed to find the shortest route.

An entrance of a passage is either unvisited, marked once or marked twice. Note that marking an entrance is not the same as marking a junction or a passage, because a junction may have multiple entrances, and a passage has an entrance at both ends. Dead ends can be thought of as junctions with one entrance (imagine there being a room at each dead end).

The algorithm works according to the following rules:

<ul><li>Whenever you pass through an entrance of a passage, whether it is to enter or exit a junction, leave a mark at the entrance as you pass.</li>

<li>When you are at a junction, use the first applicable rule below to pick an entrance to exit through:

<ol><li>If only the entrance you just came from is marked, pick an arbitrary unmarked entrance, if any. This rule also applies if you're just starting in the middle of the maze and there are no marked entrances at all.</li>

<li>If all entrances are marked, go back through the entrance you just came from, unless it is marked twice. This rule will apply whenever you reach a dead end.</li>

<li>Pick any entrance with the fewest marks (zero if possible, else one).</li></ol></li></ul>

The "turn around and return" rule effectively transforms any maze with loops into a simply connected one; whenever we find a path that would close a loop, we treat it as a dead end and return. Without this rule, it is possible to cut off one's access to still-unexplored parts of a maze if, instead of turning back, we arbitrarily pick another entrance.

When you finally reach the solution, entrances marked exactly once will indicate a way back to the start. If there is no exit, this method will take you back to the start where all entrances are marked twice.

In this case each passage is walked down exactly twice, once in each direction. The resulting <a href="Glossary_of_graph_theory#Walks" title="Glossary of graph theory">walk</a> is called a bidirectional double-tracing.<a href="#cite_note-Eulerian_Graphs_and_related_Topics-8">[8]</a>

Essentially, this algorithm, which was discovered in the 19th century, has been used about a hundred years later as <a href="Depth-first_search" title="Depth-first search">depth-first search</a>.<a href="#cite_note-9">[9]</a><a href="#cite_note-10">[10]</a>

<div class="mw-heading mw-heading2"><h2 id="Dead-end_filling">Dead-end filling</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox" style="clear: right; float:right;margin:0 0 1.5em 1.5em"><tbody><tr><th colspan="2" class="infobox-above" style="font-size:115%">External videos</th></tr><tr><td colspan="2" class="infobox-full-data" style="text-align: left"> <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=yqZDYcpCGAI">Maze Strategy: Dead End Filling</a></td></tr><tr><td colspan="2" class="infobox-full-data" style="text-align: left"> <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=FkueaIT6RSU">Maze Solving algorithm</a></td></tr></tbody></table>

Dead-end filling is an algorithm for solving mazes that fills all dead ends, leaving only the correct ways unfilled. It can be used for solving mazes on paper or with a computer program, but it is not useful to a person inside an unknown maze since this method looks at the entire maze at once. The method is to

<li>"fill in" the path from each dead-end until the first junction is met.</li></ol>

Note that some passages won't become parts of dead end passages until other dead ends are removed first. A video of dead-end filling in action can be seen to the right.

Dead-end filling cannot accidentally "cut off" the start from the finish since each step of the process preserves the topology of the maze. Furthermore, the process won't stop "too soon" since the result cannot contain any dead-ends. Thus if dead-end filling is done on a perfect maze (maze with no loops), then only the solution will remain. If it is done on a partially braid maze (maze with some loops), then every possible solution will remain but nothing more. <a rel="nofollow" class="external autonumber" href="http://www.astrolog.org/labyrnth/algrithm.htm">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Recursive_algorithm">Recursive algorithm</h2></div>

If given an omniscient view of the maze, a simple recursive algorithm can tell one how to get to the end. The algorithm will be given a starting X and Y value. If the X and Y values are not on a wall, the method will call itself with all adjacent X and Y values, making sure that it did not already use those X and Y values before. If the X and Y values are those of the end location, it will save all the previous instances of the method as the correct path.

This is in effect a depth-first search expressed in term of grid points. The omniscient view prevents entering loops by memorization. Here is a sample code in <a href="Java_(programming_language)" title="Java (programming language)">Java</a>:

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr" dir="ltr"><pre>boolean[][] maze = new boolean[width][height]; // The maze

boolean[][] wasHere = new boolean[width][height];

boolean[][] correctPath = new boolean[width][height]; // The solution to the maze

int startX, startY; // Starting X and Y values of maze

int endX, endY; // Ending X and Y values of maze

public void solveMaze() {

maze = generateMaze(); // Create Maze (false = path, true = wall)

// Below assignment to false is redundant as Java assigns array elements to false by default, but it is included because other languages may not behave the same.

for (int row = 0; row < maze.length; row++)

// Sets boolean Arrays to default values

for (int col = 0; col < maze[row].length; col++){

wasHere[row][col] = false;

correctPath[row][col] = false;

}

boolean b = recursiveSolve(startX, startY);

// Will leave you with a boolean array (correctPath)

// with the path indicated by true values.

// If b is false, there is no solution to the maze

}

public boolean recursiveSolve(int x, int y) {

if (x == endX && y == endY) return true; // If you reached the end

if (maze[x][y] || wasHere[x][y]) return false;

// If you are on a wall or already were here

wasHere[x][y] = true;

if (recursiveSolve(x-1, y)) { // Recalls method one to the left

correctPath[x][y] = true; // Sets that path value to true;

return true;

}

if (recursiveSolve(x+1, y)) { // Recalls method one to the right

return true;

}

if (y != 0) // Checks if not on top edge

if (recursiveSolve(x, y-1)) { // Recalls method one up

return true;

}

if (y != height - 1) // Checks if not on bottom edge

if (recursiveSolve(x, y+1)) { // Recalls method one down

return true;

}

return false;

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Maze-routing_algorithm">Maze-routing algorithm</h2></div>

The maze-routing algorithm <a href="#cite_note-11">[11]</a> is a low overhead method to find the way between any two locations of the maze. The algorithm is initially proposed for <a href="Chip_multiprocessor" class="mw-redirect" title="Chip multiprocessor">chip multiprocessors</a> (CMPs) domain and guarantees to work for any grid-based maze. In addition to finding paths between two locations of the grid (maze), the algorithm can detect when there is no path between the source and destination. Also, the algorithm is to be used by an inside traveler with no prior knowledge of the maze with fixed memory complexity regardless of the maze size; requiring 4 variables in total for finding the path and detecting the unreachable locations. Nevertheless, the algorithm is not to find the shortest path.

Maze-routing algorithm uses the notion of <a href="Manhattan_distance" class="mw-redirect" title="Manhattan distance">Manhattan distance</a> (MD) and relies on the property of grids that the MD increments/decrements exactly by 1 when moving from one location to any 4 neighboring locations. Here is the pseudocode without the capability to detect unreachable locations.

<div class="mw-highlight mw-highlight-lang-c++ mw-content-ltr" dir="ltr"><pre>Point src, dst;// Source and destination coordinates

// cur also indicates the coordinates of the current location

int MD_best = MD(src, dst);// It stores the closest MD we ever had to dst

// A productive path is the one that makes our MD to dst smaller

while (cur != dst) {

if (there exists a productive path) {

Take the productive path;

} else {

MD_best = MD(cur, dst);

Imagine a line between cur and dst;

Take the first path in the left/right of the line; // The left/right selection affects the following hand rule

while (MD(cur, dst) != MD_best || there does not exist a productive path) {

Follow the right-hand/left-hand rule; // The opposite of the selected side of the line

}

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Shortest_path_algorithm">Shortest path algorithm</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Pathfinding#Algorithms" title="Pathfinding">Pathfinding § Algorithms</a></div>

When a maze has multiple solutions, the solver may want to find the shortest path from start to finish. There are several algorithms to find shortest paths, most of them coming from <a href="Graph_theory" title="Graph theory">graph theory</a>. One such algorithm finds the shortest path by implementing a <a href="Breadth-first_search" title="Breadth-first search">breadth-first search</a>, while another, the <a href="A*_algorithm" class="mw-redirect" title="A* algorithm">A* algorithm</a>, uses a <a href="Heuristic" title="Heuristic">heuristic</a> technique. The breadth-first search algorithm uses a <a href="Queue_(data_structure)" class="mw-redirect" title="Queue (data structure)">queue</a> to visit cells in increasing distance order from the start until the finish is reached. Each visited cell needs to keep track of its distance from the start or which adjacent cell nearer to the start caused it to be added to the queue. When the finish location is found, follow the path of cells backwards to the start, which is the shortest path. The breadth-first search in its simplest form has its limitations, like finding the shortest path in weighted graphs.

<div class="mw-heading mw-heading2"><h2 id="Multi-agent_maze-solving">Multi-agent maze-solving</h2></div>

Collective exploration refers to the exploration of an unknown environment by multiple mobile agents that move at the same speed. This model was introduced

to study the <a href="Parallel_computing" title="Parallel computing">paralellizability</a> of maze-solving,<a href="#cite_note-Fraigniaud2006-12">[12]</a> especially in the case of <a href="Tree_(graph_theory)" title="Tree (graph theory)">trees</a>. The study depends on the model of communication between the agents. In the centralized communication model, the agents are allowed to communicate at all times with one another. In the <a href="Distributed_computing" title="Distributed computing">distributed</a> communication model, the agents can communicate only by reading and writing on the walls of the maze. For trees with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> nodes and depth <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy">, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> robots, the current-best algorithm is in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left({\frac {n}{k}}+kD\right)}">

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left({\frac {n}{k}}+kD\right)}</annotation>

</semantics>

</math><img src="./1fb3d56973b1d9f58c92cbfc92cc3687587d9135.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:13.143ex; height:5.009ex;" alt="{\displaystyle O\left({\frac {n}{k}}+kD\right)}" loading="lazy"> in the centralized communication model and in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left({\frac {n}{\log k}}+D\right)}">

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left({\frac {n}{\log k}}+D\right)}</annotation>

</semantics>

</math><img src="./19505064a597080e109cf28a55ef41ed8dae3ca3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:15.752ex; height:6.176ex;" alt="{\displaystyle O\left({\frac {n}{\log k}}+D\right)}" loading="lazy"> in the distributed communication model.<a href="#cite_note-Fraigniaud2006-12">[12]</a>

<li><a href="Maze_generation_algorithm" title="Maze generation algorithm">Maze generation algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=k1tSK5V1pds">Maze to Tree</a> on <a href="YouTube_video_(identifier)" class="mw-redirect" title="YouTube video (identifier)">YouTube</a>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAleliunasKarpLiptonLovász1979" class="citation conference cs1">Aleliunas, Romas; Karp, Richard M; Lipton, Richard J; Lovász, László; Rackoff, Charles (1979). "Random walks, universal traversal sequences, and the complexity of maze problems". 20th Annual Symposium on Foundations of Computer Science (sfcs 1979). IEEE Computer Society. pp. 218–223.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=IIBwiGrUgzc">Maze Transformed</a> on <a href="YouTube_video_(identifier)" class="mw-redirect" title="YouTube video (identifier)">YouTube</a>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFAbelsondiSessa1980" class="citation cs2">Abelson; diSessa (1980), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=3geYp44hJVcC">Turtle Geometry: the computer as a medium for exploring mathematics</a>, MIT Press, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780262510370</bdi></cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Seymour Papert, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170706130427/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-298.pdf">"Uses of Technology to Enhance Education"</a>, MIT Artificial Intelligence Memo No. 298, June 1973

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> Public conference, December 2, 2010 – by professor Jean Pelletier-Thibert in Academie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0980-6032">0980-6032</a>) Charles Tremaux (° 1859 – † 1882) Ecole Polytechnique of Paris (X:1876), French engineer of the telegraph

</li>

<li id="cite_note-Récréations_Mathématiques-7"><a href="#cite_ref-Récréations_Mathématiques_7-0">^</a> Édouard Lucas: Récréations Mathématiques Volume I, 1882.

</li>

<li id="cite_note-Eulerian_Graphs_and_related_Topics-8"><a href="#cite_ref-Eulerian_Graphs_and_related_Topics_8-0">^</a> H. Fleischner: Eulerian Graphs and related Topics. In: Annals of Discrete Mathematics No. 50 Part 1 Volume 2, 1991, page X20.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFEven2011" class="citation cs2"><a href="Shimon_Even" title="Shimon Even">Even, Shimon</a> (2011), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=m3QTSMYm5rkC&pg=PA46">Graph Algorithms</a> (2nd ed.), Cambridge University Press, pp. 46–48, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-73653-4</bdi></cite>.

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFSedgewick2002" class="citation cs2">Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (3rd ed.), Pearson Education, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-201-36118-6</bdi></cite>.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFFattahet2015" class="citation book cs1">Fattah, Mohammad; et, al. (2015-09-28). <a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=2786591">"A Low-Overhead, Fully-Distributed, Guaranteed-Delivery Routing Algorithm for Faulty Network-on-Chips"</a>. Proceedings of the 9th International Symposium on Networks-on-Chip. Nocs '15. pp. 1–8. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2786572.2786591">10.1145/2786572.2786591</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781450333962</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17741498">17741498</a>.</cite>

</li>

<li id="cite_note-Fraigniaud2006-12">^ <a href="#cite_ref-Fraigniaud2006_12-0">a</a> <a href="#cite_ref-Fraigniaud2006_12-1">b</a> <cite id="CITEREFFraigniaudGasieniecKowalskiPelc2006" class="citation journal cs1">Fraigniaud, Pierre; Gasieniec, Leszek; Kowalski, Dariusz R; Pelc, Andrzej (2006). "Collective tree exploration". Networks. 48 (3). Wiley Online Library: 166–177. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fnet.20127">10.1002/net.20127</a>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.astrolog.org/labyrnth/algrithm.htm#solve">Think Labyrinth: Maze algorithms</a> (details on these and other maze-solving algorithms)</li>

<li><a rel="nofollow" class="external text" href="http://www.cb.uu.se/~cris/blog/index.php/archives/277">MazeBlog: Solving mazes using image analysis</a></li>

<li><a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=jhL8uELbVIM">Video: Maze solving simulation</a></li>

<li>Simon Ayrinhac, <a rel="nofollow" class="external text" href="http://iopscience.iop.org/article/10.1088/0031-9120/49/4/443">Electric current solves mazes</a>, © 2014 IOP Publishing Ltd.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-22" href="https://en.wikipedia.org/wiki/?title=Maze-solving_algorithm&oldid=1301937400">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>